package leetcode.editor.cn.dsa25_toposort;
//给定一个整数矩阵，找出最长递增路径的长度。
// 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
//
// 示例 1: 
// 输入: nums =
//[
//  [9,9,4],
//  [6,6,8],
//  [2,1,1]
//] 
//输出: 4 
//解释: 最长递增路径为 [1, 2, 6, 9]。 
//
// 示例 2: 
// 输入: nums =
//[
//  [3,4,5],
//  [3,2,6],
//  [2,2,1]
//] 
//输出: 4 
//解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
// 
// Related Topics 深度优先搜索 拓扑排序 记忆化 
// 👍 401 👎 0

public class LongestIncreasingPathInAMatrix329_1 {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int m, n; // 矩阵的长和宽
        // 以当前节点为坐标中心，分别向左右上下四个方向查找邻接点
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int[][] longestPath; // 记录从各个节点出发的最长路径的长度
        public int longestIncreasingPath(int[][] matrix) {
            if ((m = matrix.length) == 0
                    ||(n = matrix[0].length) == 0) return 0;
            longestPath = new int[m][n];
            int res = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 取最长的路径
                    res = Math.max(res, dfs(matrix, i, j));
                }
            }
            return res;
        }
        // 求从[i,j]节点出发的最长递增路径长度
        private int dfs(int[][] matrix, int row, int column) {
            // 该节点已经被扩展过，则返回其最长路径
            if (longestPath[row][column] != 0)
                return longestPath[row][column];
            int ans = 0;
            for (int[] dir : dirs) { // 朝四个方向遍历邻居节点
                // 邻居节点的坐标
                int newRow = row + dir[0], newColumn = column + dir[1];
                // 如果邻居元素存在，且比当前元素大，说明存在边
                if (newRow >= 0 && newRow < m && newColumn >= 0 && newColumn < n
                        && matrix[newRow][newColumn] > matrix[row][column]) {
                    ans = Math.max(ans, dfs(matrix, newRow, newColumn));
                }
            }
            // 最长路径长度 = 上下左右方向的最长路径长度 + 当前节点长度1
            return longestPath[row][column] = ans + 1;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}